package sort

type QuickSort struct {
	BaseSort
}

func (self QuickSort) Sort() {
	self.sort(self.Array, 0, self.Len()-1)
}

//递归实现排序
func (self QuickSort) sort(array []int, left, right int) {
	// 递归结束条件
	if left >= right {
		return
	}

	//标定点所处的位置索引
	p := self.partition(array, left, right)
	self.sort(array, left, p-1)
	self.sort(array, p+1, right)

}

// 重点在选取标定点，分成小于标定点分段与大于标定点的分段,逐步排序
func (self QuickSort) partition(array []int, left, right int) int {
	v := array[left]

	j := left
	for i := left + 1; i <= right; i++ {
		if array[i] < v {
			j++
			array[i], array[j] = array[j], array[i]
		}

	}
	array[j], array[left] = array[left], array[j]
	return j

}

func (self QuickSort) Name() string {
	return "快速排序"
}
